package com.example.question.dp.dp2;

/**
 * @Date 2023-07-22
 * @Author Jonathan
 * @Description 0-1背包问题
 */
public class Code06_Knapsack {

    public static void main(String[] args) {
//        dfs(new int[]{3, 4, 5}, new int[]{15, 10, 12}, 10, 0, -1);
//        System.out.println(max);
        int[] w = new int[]{3, 4, 5};
        int[] v = new int[]{10, 15, 12};
        int c = 10;
        int f = f(new int[]{3, 4, 5}, new int[]{15, 10, 12}, 10, 2, 0);
        System.out.println(f);
        int f1 = f1(new int[]{3, 4, 5}, new int[]{15, 10, 12}, 10, 0, 0);
        System.out.println(f1);
        f1 = f3(new int[]{3, 4, 5}, new int[]{15, 10, 12}, 10, -1);
        System.out.println(f1);
        int f4 = f4(new int[]{3, 4, 5}, new int[]{15, 10, 12}, 10, 0);
        System.out.println("f4 = " + f4);
        int f5 = f5(w, v, c, 0);
        System.out.println("f5 = " + f5);
    }

    public void knapsack(int[] weights, int[] values, int capacity) {

    }

    /**
     * 边界条件是什么？
     * (物品索引，剩余容量，积累价值)
     * 这个怎么抽象成树形？
     */
    static int max = 0;
    static int total = 0;

    private static void dfs(int[] weights, int[] values, int capacity, int total, int startIndex) {
        // 容量不够的剪枝
//        if (startIndex >= weights.length) {
//            return;
//        }
//        if (capacity < 0) {
//            return;
//        }
        max = Math.max(max, total);
//        // 用索引剪枝
//        for (int i = startIndex; i < weights.length; i++) {
//            // 剪枝
//            dfs(weights, values, capacity - weights[i], total + values[i], i + 1);
//        }
        for (int i = startIndex; i < weights.length; i++) {
            int childIndex = i + 1;
            // 剪枝
            if (childIndex == weights.length) {
                continue;
            }
            // 剪枝
            if (capacity < weights[childIndex]) {
                continue;
            }
            dfs(weights, values, capacity - weights[childIndex], total + values[childIndex], childIndex);
        }
    }


    private static int f(int[] weights, int[] values, int capacity, int index, int totalVal) {
        if (index < 0) {
            return totalVal;
        }
        int res1 = 0;
        int res2;
        // 要
        // 要的话  需要容量还够
        if (capacity > weights[index]) {
            res1 = f(weights, values, capacity - weights[index], index - 1, totalVal + values[index]);

        }
        // 不要 那就看下一个了
        res2 = f(weights, values, capacity, index - 1, totalVal);
        return Math.max(res1, res2);
    }


    private static int f1(int[] weights, int[] values, int capacity, int index, int totalVal) {
        if (index >= weights.length) {
            return totalVal;
        }
        int res1 = 0;
        int res2;
        // 偷
        // 偷的话 需要容量还够
        if (capacity > weights[index]) {
            res1 = f1(weights, values, capacity - weights[index], index + 1, totalVal + values[index]);

        }
        // 不偷
        res2 = f1(weights, values, capacity, index + 1, totalVal);
        return Math.max(res1, res2);
    }

    private static int f2(int[] weights, int[] values, int capacity, int index, int totalVal) {
        if (index < 0 || capacity < 0) {
            return totalVal;
        }
        int res1 = 0;
        int res2;
        // 要
        // 要的话  需要容量还够
        if (capacity > weights[index]) {
            res1 = f2(weights, values, capacity - weights[index], index - 1, totalVal + values[index]);

        }
        // 不要 那就看下一个了
        res2 = f2(weights, values, capacity, index - 1, totalVal);
        return Math.max(res1, res2);
    }

    private static int f3(int[] weights, int[] values, int capacity, int startIndex) {
        int totalValue = 0;
        for (int i = startIndex; i < weights.length; i++) {
            int childIndex = i + 1;
            // 剪枝
            if (childIndex == weights.length) {
                continue;
            }
            // 剪枝
            if (capacity < weights[childIndex]) {
                continue;
            }
            int childMaxValue = f3(weights, values, capacity - weights[childIndex], childIndex);
            totalValue = Math.max(childMaxValue, totalValue);
        }
        // 根节点的值是不需要加上去的
        return (startIndex == -1 ? 0 : values[startIndex]) + totalValue;
    }


    private static int f4(int[] w, int[] v, int c, int index) {
        if (index == w.length) {
            return 0;
        }
        int totalValue = 0;
        for (int i = index; i < w.length; i++) {
            // 剪枝
            if (c < w[i]) {
                continue;
            }
            int childValue = f4(w, v, c - w[i], i + 1);
            int childMaxValue = childValue + v[i];
            totalValue = Math.max(childMaxValue, totalValue);
        }
        return totalValue;
    }


    private static int f5(int[] weights, int[] values, int capacity, int index) {
        // 边界条件
        if (index >= weights.length) {
            return 0;
        }
        int max = 0;
        for (int i = index; i < weights.length; i++) {
            // 剪枝之后 就过滤掉装不下的了
            if (capacity < weights[i]) {
                continue;
            }
            int val = f5(weights, values, capacity - weights[i], i + 1) + values[i];
            max = Math.max(val, max);
        }
        return max;
    }


    private static int dfs1(int[] weights, int[] values, int capacity, int startIndex) {
        // 容量不够的剪枝

        int res = Integer.MIN_VALUE;
        // 用索引剪枝
        for (int i = startIndex; i < weights.length; i++) {
            if (startIndex + 1 == weights.length) {
                continue;
            }
            capacity -= weights[startIndex];
            startIndex += 1;

            int sum = dfs1(weights, values, capacity, startIndex);
            res = Math.max(res, sum);

            capacity += weights[startIndex];
            startIndex -= 1;

        }
        return res + /*startIndex == 0 ? 0 :*/ values[startIndex];
    }
}
